2200+专项：E1、E2. Nauuo and Pictures (easy and hard version)（搜索概率）

2023-08-05 03:39| 来源: 网络整理| 查看: 265

原题： http://codeforces.com/contest/1173/problem/E1

题意：

有n个数，值w，add=1表示喜欢，=0表示不喜欢。

抽m次，每个数被抽到的概率为 w i ∑ w \dfrac{w_i}{\sum w} ∑wwi。被抽到后，如果喜欢w+1，否则w-1。

问结束后每个数最后的期望值。

解析：

对于每个数做一次，分为三块：自己，其他的喜欢的，其他的不喜欢。用 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示三块加了 i , j , k i,j,k i,j,k次的概率， v a l [ i ] [ j ] [ k ] val[i][j][k] val[i][j][k]表示三块加了 i , j , k i,j,k i,j,k次，概率为 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]下的期望。

下一次做到这个状态，只需要用当前的概率和记录下的概率 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]算一下就得出需要加的期望了。

比赛结束后2分钟找出bug，不爽

代码：

#include using namespace std; #define LL long long const int maxn=59; const LL mod=998244353; int add[maxn]; LL w[maxn]; LL dp[52][52][52]; LL val[52][52][52]; bool vis[52][52][52]; LL Pow(LL a,LL b){ LL res=1; a%=mod; while(b){ if(b&1)res=res*a%mod; b>>=1; a=a*a%mod; }return res; } inline LL inv(LL a){ return Pow(a,mod-2); } int flag; LL dfs(int step,LL p,int i,int j,int k,LL x,LL y,LL z){ if(step==0)return p*x%mod; if(vis[i][j][k]){ return val[i][j][k]*inv(dp[i][j][k])%mod*p%mod; } dp[i][j][k]=p; val[i][j][k]+=dfs(step-1,p*x%mod*inv(x+y+z)%mod,i+1,j,k,max(0ll,x+flag),y,z); val[i][j][k]+=dfs(step-1,p*y%mod*inv(x+y+z)%mod,i,j+1,k,x,y+1,z); val[i][j][k]+=dfs(step-1,p*z%mod*inv(x+y+z)%mod,i,j,k+1,x,y,max(0ll,z-1)); val[i][j][k]%=mod; vis[i][j][k]=1;// return val[i][j][k]; } int main(){ int n,m;scanf("%d%d",&n,&m); LL ori,s0=0,s1=0; for(int i=1;i memset(dp,0,sizeof dp); memset(val,0,sizeof val); memset(vis,0,sizeof vis); //dp[0][0][0]=1; if(add[i]) flag=1, val[0][0][0]=dfs(m,1,0,0,0,w[i],s1-w[i],s0); else flag=-1, val[0][0][0]=dfs(m,1,0,0,0,w[i],s1,s0-w[i]); printf("%lld\n",val[0][0][0]); } } HARD version

变难版本后，n为2e5，m为3e3。

我们再来分析选择时的可能性。

喜欢的用x表示，不喜欢的用y表示，则有： x 1 , x 2 . . . y 1 , y 2 . . . x_1,x_2...y_1,y_2... x1,x2...y1,y2...

选择任意一个x后，总值都变为 ∑ x + ∑ y + 1 \sum_x+\sum_y+1 ∑x+∑y+1，喜欢的数所占权重都为 ∑ x + 1 \sum_x+1 ∑x+1。所以可以得出结论：选择哪个都无所谓。

所以假设m次操作后， ∑ x \sum_x ∑x的期望值为 X X X，那么 x i x_i xi的期望值就是 x i X ∑ x x_i\dfrac{X}{\sum_x} xi∑xX

这个用dp做就是：用 d p [ i ] [ j ] dp[i][j] dp[i][j]表示选 i i i次喜欢的， j j j次不喜欢的概率，那么就有 X = ∑ x + ∑ i = 0 m d p [ i ] [ m − i ] ∗ i X=\sum x+\sum_{i=0}^mdp[i][m-i]*i X=∑x+i=0∑mdp[i][m−i]∗i

inv数组好像要预处理才行，下标变一下就行

#include using namespace std; #define LL long long const int maxn=2e5+9; const int maxm=3e3+9; const LL mod=998244353; int add[maxn]; LL w[maxn]; LL dp[maxm][maxm]; LL Pow(LL a,LL b){ LL res=1; a%=mod; while(b){ if(b&1)res=res*a%mod; b>>=1; a=a*a%mod; }return res; } inline LL inv(LL a){ return Pow(a,mod-2); } LL INV[2*maxm]; int main(){ int n,m;scanf("%d%d",&n,&m); LL s0=0,s1=0,inv0,inv1; for(int i=1;i if(s0+s1+i dp[j][i-j]=(j==0)?0: (dp[j-1][i-j]*(s1+j-1)%mod*INV[j-1-(i-j)+maxm]%mod); dp[j][i-j]+=(i-j==0)?0: (dp[j][i-j-1]*(s0-(i-j-1))%mod*INV[j-(i-j-1)+maxm]%mod); dp[j][i-j]%=mod; } } LL ans[2]={0,0}; for(int i=0;i if(add[i]){ printf("%d\n",w[i]*ans[1]%mod*inv1%mod); } else{ printf("%d\n",w[i]*ans[0]%mod*inv0%mod); } } }

【本文地址】

公司简介

联系我们

2200+专项：E1、E2. Nauuo and Pictures (easy and hard version)（搜索 概率）

2200+专项：E1、E2. Nauuo and Pictures (easy and hard version)（搜索概率）